/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 */
class Solution3 {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        int n = nums.length;
        int left = 0, right = n - 1;

        // 寻找区间左端点
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else {
                // nums[mid] >= target
                right = mid;
            }
        }
        if(left == right && nums[left] == target) ret[0] = left;

        left = 0;
        right = n - 1;

        // 寻找区间右端点
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) {
                right = mid - 1;
            } else {
                // nums[mid] <= target
                left = mid;
            }
        }

        if(left == right && nums[left] == target) ret[1] = left;

        return ret;
    }
}